package three;
import java.util.*;
public class A056 {

    public static void main(String[] args) {
        //letterCombinations("23");
    }

    List<String> ret = new ArrayList<>();
    Map<Character,String> map = new HashMap<>();
    StringBuilder path = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")) return ret;
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

        dfs(digits.toCharArray(),0);
        return ret;
    }
    public void dfs(char[] str,int pos) {
        //1.终止条件：遍历完str
        if(pos >= str.length ) {
            ret.add(new String(path));
            return;
        }
        //2.
        String cur = map.getOrDefault(str[pos],"");
        for(int i=0;i<cur.length();i++) {
            path.append(cur.charAt(i));
            dfs(str,pos+1);
            //回溯
            path.deleteCharAt(pos);
        }
    }

}
